# 从前序与中序遍历序列构造二叉树

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        return self.build(preorder, inorder)

    def build(self, preorder, inorder):
        if not preorder:
            return None
        root = preorder[0]
        node = TreeNode(root)
        # 根据中序遍历分为左右子树
        global i
        for i in range(len(inorder)):
            if inorder[i] == root:
                break
        left_inorder = inorder[0:i]
        right_inorder = inorder[i+1:len(inorder)]
        # 把先序也分为左右子树
        # if left_inorder:
        #     for j in range(len(preorder)):
        #         if preorder[j] == left_inorder[-1]:
        #             break
        #     left_preorder = preorder[1:j+1]
        #     right_preorder = preorder[j+1:len(preorder)]
        # else:
        #     left_preorder = []
        #     right_preorder = preorder[1:len(preorder)]
        left_preorder = preorder[1: 1+len(left_inorder)]
        right_preorder = preorder[1+len(left_inorder):len(preorder)]
        node.left = self.build(left_preorder, left_inorder)
        node.right = self.build(right_preorder, right_inorder)
        return node


preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]

# s = Solution()
# s.buildTree(preorder, inorder)

for i in range(len(inorder)):
    if inorder[i] == 3:
        break
left_inorder = inorder[0:i]
right_inorder = inorder[i+1:len(inorder)]
print(left_inorder)
print(right_inorder)
# for j in range(len(preorder)):
#     if preorder[j] == left_inorder[-1]:
#         break
# left_preorder = preorder[1:j+1]
# right_preorder = preorder[j+1:len(preorder)]
# print(left_preorder)
# print(right_preorder)

left_preorder = preorder[1: 1+len(left_inorder)]
right_preorder = preorder[1+len(left_inorder):len(preorder)]
print(left_preorder)
print(right_preorder)
